ট্রাভার্সাল মেথড (Traversal Methods)
ট্রি ডেটা স্ট্রাকচারে ট্রাভার্সাল হল একটি প্রক্রিয়া যার মাধ্যমে আমরা ট্রির সমস্ত নোডগুলি ভিজিট করি। প্রধান তিনটি ট্রাভার্সাল মেথড হল ইনঅর্ডার (In-order), প্রি-অর্ডার (Pre-order), এবং পোস্ট-অর্ডার (Post-order)। প্রতিটি পদ্ধতির নিজস্ব ব্যবহার এবং বৈশিষ্ট্য রয়েছে।
১. ইনঅর্ডার ট্রাভার্সাল (In-order Traversal)
বর্ণনা
ইনঅর্ডার ট্রাভার্সালে, প্রথমে বাম সাবট্রি, তারপর মূল (root) নোড, এবং তারপর ডান সাবট্রি পরিদর্শন করা হয়। এই পদ্ধতি সাধারণত বাইনারি সার্চ ট্রির জন্য ব্যবহার করা হয়, কারণ এটি সব নোডকে সজ্জিতকৃত (sorted) অর্ডারে বের করে।
উদাহরণ
- বাম সাবট্রি
- মূল নোড
- ডান সাবট্রি
উদাহরণ কোড (Python):
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def in_order(root):
if root:
in_order(root.left)
print(root.val, end=' ')
in_order(root.right)
# ট্রি তৈরি করা
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("In-order Traversal:")
in_order(root) # Output: 4 2 5 1 3
২. প্রি-অর্ডার ট্রাভার্সাল (Pre-order Traversal)
বর্ণনা
প্রি-অর্ডার ট্রাভার্সালে, প্রথমে মূল নোড, তারপর বাম সাবট্রি এবং তারপর ডান সাবট্রি পরিদর্শন করা হয়। এটি সাধারণত ডেটা স্ট্রাকচারের কপি তৈরি করার জন্য ব্যবহার করা হয়।
উদাহরণ
- মূল নোড
- বাম সাবট্রি
- ডান সাবট্রি
উদাহরণ কোড (Python):
def pre_order(root):
if root:
print(root.val, end=' ')
pre_order(root.left)
pre_order(root.right)
print("\nPre-order Traversal:")
pre_order(root) # Output: 1 2 4 5 3
৩. পোস্ট-অর্ডার ট্রাভার্সাল (Post-order Traversal)
বর্ণনা
পোস্ট-অর্ডার ট্রাভার্সালে, প্রথমে বাম সাবট্রি, তারপর ডান সাবট্রি এবং পরে মূল নোড পরিদর্শন করা হয়। এটি সাধারণত মেমরি মুক্ত করার বা ট্রির নির্মাণের জন্য ব্যবহৃত হয়।
উদাহরণ
- বাম সাবট্রি
- ডান সাবট্রি
- মূল নোড
উদাহরণ কোড (Python):
def post_order(root):
if root:
post_order(root.left)
post_order(root.right)
print(root.val, end=' ')
print("\nPost-order Traversal:")
post_order(root) # Output: 4 5 2 3 1
উপসংহার
ইনঅর্ডার, প্রি-অর্ডার, এবং পোস্ট-অর্ডার ট্রাভার্সাল হল ট্রি ডেটা স্ট্রাকচার ব্যবহারের মৌলিক পদ্ধতি। প্রতিটি পদ্ধতির নিজস্ব বৈশিষ্ট্য এবং ব্যবহার রয়েছে, যা বিভিন্ন পরিস্থিতিতে উপকারী হতে পারে। এই ট্রাভার্সাল পদ্ধতিগুলি ডেটা স্ট্রাকচারের বিভিন্ন কার্যকারিতা এবং অ্যালগরিদমগুলির উন্নয়নে অত্যন্ত গুরুত্বপূর্ণ।
